﻿#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<ctype.h>
#include<string.h>
using namespace std;

//int main()
//{
//	char str[] = "This is a simple string";
//	char* pch;
//	pch = strstr(str, "simple");
//	strncpy(pch, "sample", 6);
//	printf("%s\n", str);
//	return 0;
//}

//struct node
	//{
	//	int e, ne;
	//
	//}list[N];


// //   单向链表
//const int N = 1e5 + 10;
//int h; // 头指针
//int id; // 下⼀个元素分配的位置
//int e[N], ne[N];
//int mp[N];
//
//
//// 遍历
//void print()
//{
//	for (int i = ne[h]; i; i = ne[i])
//	{
//		cout << e[i] << " ";
//	}
//	cout << endl << endl;
//}
//
//// 头插
//void push_front(int x)
//{
//	id++;
//	e[id] = x;
//	mp[x] = id;// 标记x存储位置；
//
//	ne[id] = ne[h];
//	ne[h] = id;
//}
//
//// 寻找一个 值的存储位置 的下标；
//int find(int x)
//{//
//	/*for (int i = ne[h]; i; i = ne[i])
//	{
//		if(e[i] == x)
//		{
//			return i;
//		}
//	}
//	return 0;*/
//	return mp[x];
//}
//
//// 存储位置为p 的元素后面插入x ，存储位置为p，但在链表的位置不一定为p
//void insert(int p, int x)
//{
//	id++;
//	e[id] = x;
//
//	mp[x] = id;
//
//	ne[id] = ne[p];
//	ne[p] = id;
//}
//
//// 删除任意位置p后面的元素；
//void erase(int p)
//{
//	if (ne[p] != 0)
//	{
//		mp[e[ne[p]]] = 0;// 清空标记
//		ne[p] = ne[ne[p]];
//	}
//}
//
//int main()
//{
//	for (int i = 1; i <= 5; i++)
//	{
//		push_front(i);
//		print();
//	}
//
//	/*cout << find(1) << endl;
//	cout << find(5) << endl;
//	cout << find(6) << endl;
//
//	insert(1, 10);
//	print();
//	insert(2, 200);
//	print();*/
//    
//	erase(2);
//	print();
//	erase(4);
//	print();
//
//	return 0;
//}




// //双向链表
//const int N = 1e5 + 10;
//int h; // 头指针
//int id; // 下⼀个元素分配的位置
//int e[N], ne[N], pre[N];
//int mp[N];// 数据无重复才可以使用mp
//
// 存储位置为p 的元素后面插入 x ，存储位置为p，但在链表的位置不一定为p
//void insert(int p, int x)
//{
//	id++;
//	e[id] = x;
//
//	mp[x] = id;
//
//	ne[id] = ne[p];
//
//	pre[ne[p]] = id;
//
//	pre[id] = p;//
//
//	ne[p] = id;
//}
//
//void insert_front(int p, int x)// 在存储位置为p的元素 前 面  插入一个新的元素x
//{
//	id++;
//	e[id] = x;
//	mp[x] = id;
//	ne[pre[p]] = id;
//	pre[id] = pre[p];
//	ne[id] = p;
//	pre[p] = id;
//}
//
//void push_front(int x)
//{
//	id++;
//
//	e[id] = x;//存
//
//	mp[x] = id;
//	 配合第一次学的时候画的图理解
//	pre[id] = h;// 图2
//
//	ne[id] = ne[h];// 图3
//
//	pre[ne[h]] = id;//图4
//
//	ne[h] = id;// 图1
//}
//
//
// 删除任意位置为p的元素；
//void erase(int p)
//{
//	mp[p] = 0;
//	pre[ne[p]] = pre[p];
//	ne[pre[p]] = ne[p];
//}
//
//int find(int x)
//{
//	return mp[x];
//}
//
//void print()
//{
//	for (int i = ne[h]; i; i = ne[i])
//	{
//		cout << e[i] << " ";
//	}
//	cout << endl << endl;
//}
//
//int main()
//{
//	for (int i = 1; i <=10; i++)
//	{
//		push_front(i);
//	}
//	print();
//	/*int ret = find(10);
//	cout << ret;*/
//
//	/*insert(8, 666);
//
//	print();
//
//	insert(7, 999);
//
//	print();
//	int ret = find(999);
//    cout << ret;*/
//
//	insert_front(10, 1000);
//	insert_front(8, 898);
//	print();
//	int ret = find(898);
//	cout << ret; 
//	erase(8);
//	print();
//	int ret = //find(8);
//	cout << ret; 
//
//
//	return 0;
//}

// // //最后一个元素指向表头就是循环链表；


